/**
 * @file
 * @author  Aapo Kyrola <akyrola@cs.cmu.edu>
 * @version 1.0
 *
 * @section LICENSE
 *
 * Copyright [2012] [Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University]
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 
 *
 * @section DESCRIPTION
 *
 * Simple implementation for single-source shortest path problem.
 */

#include <string>
#include "graphchi_basic_includes.hpp"
#include "util/seqlist.hpp"

using namespace graphchi;

#define NITERS 100

/**
  * Type definitions. Remember to create suitable graph shards using the
  * Sharder-program. 
  */
typedef int VertexDataType;
typedef int EdgeDataType;

/**
  * GraphChi programs need to subclass GraphChiProgram<vertex-type, edge-type> 
  * class. The main logic is usually in the update function.
  */
struct ShortestProgram : public GraphChiProgram<VertexDataType, EdgeDataType> {
    
	int N;
	int INFINITY;
	
	int change;
	
    /**
     *  Vertex update function.
     */
    void update(graphchi_vertex<VertexDataType, EdgeDataType> &vertex, graphchi_context &ginfo) 
    {
		if (ginfo.iteration == 0) 
		{		
			change = 1;
			if (vertex.id() == 0)
			{						
				for(int i=0; i < vertex.num_edges(); i++) 
				{
					graphchi_edge<int> * edge = vertex.edge(i);
					edge->set_data(1);
				}
				vertex.set_data(0);
			}
			else
			{			
				vertex.set_data(INFINITY);
				for(int i=0; i < vertex.num_edges(); i++) 
				{
					graphchi_edge<int> * edge = vertex.edge(i);
					if(edge->get_data() == 0)
						edge->set_data(INFINITY);
				}
			}
		}
		else
		{
			int min = INFINITY;
			for(int i=0; i < vertex.num_edges(); i++)
			{
				if(vertex.edge(i)->get_data() < min)
					min = vertex.edge(i)->get_data();
			}
			if(min < vertex.get_data()-1)
			{
				vertex.set_data(min+1);
				change = 1;
			}
			for(int i=0; i < vertex.num_edges(); i++)
			{
				if(vertex.get_data() < vertex.edge(i)->get_data()) 
					vertex.edge(i)->set_data(vertex.get_data());
			}
		}		
    }
    
    /**
     * Called before an iteration starts.
     */
    void before_iteration(int iteration, graphchi_context &gcontext) {
		N = gcontext.nvertices;
		INFINITY = N;
		change = 0;
		gcontext.set_last_iteration(NITERS);
    }
    
    /**
     * Called after an iteration has finished.
     */
    void after_iteration(int iteration, graphchi_context &gcontext) {
		if(change == 0)
			gcontext.set_last_iteration(iteration);
    }
    
    /**
     * Called before an execution interval is started.
     */
    void before_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {        
    }
    
    /**
     * Called after an execution interval has finished.
     */
    void after_exec_interval(vid_t window_st, vid_t window_en, graphchi_context &gcontext) {        
    }
};

int main(int argc, const char ** argv) {
    /* GraphChi initialization will read the command line 
       arguments and the configuration file. */
    graphchi_init(argc, argv);    
    /* Metrics object for keeping track of performance counters
       and other information. Currently required. */
    metrics m("shortest");    
    /* Basic arguments for application */
    std::string filename = get_option_string("file");  // Base filename
    bool scheduler       = get_option_int("scheduler", 0); // Whether to use selective scheduling    
    /* Detect the number of shards or preprocess an input to create them */
    int nshards          = convert_if_notexists<EdgeDataType>(filename, get_option_string("nshards", "auto"));
    /* Run */
    ShortestProgram program;
    graphchi_engine<VertexDataType, EdgeDataType> engine(filename, nshards, scheduler, m); 
    engine.run(program, NITERS);
    /* Output top ranked vertices */
    std::vector< vertex_value<int> > top = get_seq_vertices<int>(filename, program.N);
    for(int i=0; i < (int)top.size(); i++) {
        std::cout << top[i].vertex << " " << top[i].value << std::endl;
    }       
    return 0;
}
